package middle;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution_365 {

    public static void main(String[] args) {
        Solution_365 model = new Solution_365();
        System.out.println(model.canMeasureWater(3, 5, 4));
        System.out.println(model.canMeasureWater(2, 6, 5));
        System.out.println(model.canMeasureWater(1, 2, 3));
    }

    private Map<Integer, Set<Integer>> map;
    private int jug1Capacity_limit, jug2Capacity_limit;

    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        map = new HashMap<>();
        jug1Capacity_limit = jug1Capacity;
        jug2Capacity_limit = jug2Capacity;
        return dps(0, 0, targetCapacity);
    }

    private boolean dps(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity < 0 || jug2Capacity < 0 || targetCapacity < 0) {
            return false;
        } else if (jug1Capacity == targetCapacity || jug2Capacity == targetCapacity || jug1Capacity + jug2Capacity == targetCapacity) {
            return true;
        }
        Set<Integer> set = map.computeIfAbsent(jug1Capacity, k -> new HashSet<>());
        if (set.contains(jug2Capacity)) {
            return false;
        }
        set.add(jug2Capacity);
        return dps(0, jug2Capacity, targetCapacity)
            || dps(jug1Capacity, 0, targetCapacity)
            || dps(jug1Capacity_limit, jug2Capacity, targetCapacity)
            || dps(jug1Capacity, jug2Capacity_limit, targetCapacity)
            || dps(Math.max(0, jug1Capacity - (jug2Capacity_limit - jug2Capacity)), Math.min(jug2Capacity_limit, jug2Capacity + jug1Capacity), targetCapacity)
            || dps(Math.min(jug1Capacity_limit, jug1Capacity + jug2Capacity), Math.max(0, jug2Capacity - (jug1Capacity_limit - jug1Capacity)), targetCapacity);
    }
}
